package com.twopointer;

import java.util.Arrays;

public class TwoSumEx {
    public static void main(String[] args) {
        int[] arr = {2, 7, 11, 16};
        int target = 23;
        int[] result = twoSum2(arr, target);
        System.out.println(Arrays.toString(result));
    }

    /**
     * O(n)
     * @param arr
     * @param target
     * @return
     */
    private static int[] twoSum2(int[] arr, int target){
        if (arr == null || arr.length == 0) return null;
        int[] result = new int[2];
        int p1 = 0;
        int p2 = arr.length -1 ;
        while (p1 < p2){
            if ((arr[p1] + arr[p2]) < target){
                p1++;
            }else if((arr[p1] + arr[p2]) > target){
                p2--;
            }else {
                result[0] = p1;
                result[1] = p2;
                break;
            }
        }
        return result;

    }

    /**
     * O(n2)
     * @param arr
     * @param target
     * @return
     */
    private static int[] twoSum1(int[] arr, int target) {
        if (arr == null || arr.length == 0) return null;

        int[] result = new int[2];

        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if ((arr[i] + arr[j]) == target){
                    result[0] = i;
                    result[1] = j;
                }
            }
        }
        return result;
    }
}
